#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
// 定义单链表
typedef struct LNode{
    ElemType data;
    struct LNode *next;// 指向下一个结点
}LNode,*LinkedList;


// 初始化单链表(带头结点)
bool initLinkedList(LinkedList &L){
    // 注意，此处的LinkedList等价于LNode*
    L = (LinkedList) malloc(sizeof(LNode));
    // 内存空间不足，初始化失败
    if(L == NULL) return false;
    // 头结点之后暂时没其他结点
    L -> next = NULL;
    return true;
}

// 头插法建立单链表(带头结点)
bool insertLinkedListBefore(LinkedList &L){
    // 先初始化空链表
   bool ret = initLinkedList(L);
   if(!ret)  return false; // 初始化失败，直接返回
   LNode* N;
   ElemType data;
   scanf("%d",&data);
   while(data != 9999){ // 以输入9999作为输入结束
        N = (LNode*) malloc(sizeof(LNode)); // 创建新结点
        N -> data = data;
        N -> next = L -> next;
        L -> next = N; // 将新结点作为头指针的尾结点
        scanf("%d",&data);
   }
    return true;
}

// 尾插法建立单链表(带头结点)
bool insertLinkedListAfter(LinkedList &L){
    // 先初始化空链表
    bool ret = initLinkedList(L);
    if(!ret)  return false; // 初始化失败，直接返回
    LNode* p;// 插入的结点
    LNode* tail = L; // 尾结点
    ElemType data;
    scanf("%d",&data);
    while(data != 9999){ // 以输入9999作为输入结束
        p = (LNode*) malloc(sizeof (LNode)); // 创建新结点
        p->data = data;
        tail->next = p;
        tail = p; // 将当前结点作为尾结点
        scanf("%d",&data);
    }
    tail -> next = NULL; // 尾结点的下一个结点为空
    return true;
}

// 在第i个位置插入元素e：带头结点的
bool insertElemByPos(LinkedList &L,int pos,ElemType elem){
    if(pos < 1 ) return false;
    LNode* p = L; // 指向当前结点
    int j = 0; // 指明当前结点处于第几个位置
    while(p != NULL && j<pos-1){ // 循环遍历获取要插入的前一个结点
        p = p->next;
        j++;
    }
    if(p == NULL) return false; // pos位置不合法
    LNode* s = (LNode*) malloc(sizeof(LNode));
    s->data = elem;
    s -> next = p->next;
    p->next = s;
    return true;
}

// 在第i个位置插入元素e：不带头结点的
bool insertElemByPosNoHead(LinkedList &L,int pos,ElemType elem){
    // 判断位置是否合法
    if(pos < 1) return false;
    // 插入到第一个结点
    if(pos == 1){
        LNode* s = (LNode*) malloc(sizeof(LNode));
        s->data = elem;
        s->next = L;
        L = s; // 头指针指向新结点
        return true;
    }
    // 指针p指向待插入位置所在的结点的前一个结点，初始时指向第一个结点
    LNode* p = L;
    int j = 1; // 指针p所指向的结点所在的位置
    while(p != NULL && j < pos-1){
        p = p->next;
        j++;
    }
    if(p == NULL) return false; // 位置不合法
    LNode* x = (LNode*) malloc(sizeof(LNode));
    x->data = elem;
    x->next = p->next;
    p->next = x;
    return true;
}

// 指定结点的后操作：在指定结点p后面插入元素e
bool insertNodeAfter(LinkedList &p,ElemType elem){
    if(p == NULL) return false; // p不合法
    LNode* s = (LNode*) malloc(sizeof(LNode));
    if( s== NULL) return false; // 内存分配失败
    s->data = elem;
    s->next = p->next;
    p->next = s;
    return true;
}

// 指定结点的前操作：在指定结点p前面插入元素e
bool insertNodeBefore(LinkedList &p,ElemType elem){
    if(p == NULL) return false; // p不合法
    LNode* s = (LNode*) malloc(sizeof(LNode));
    if( s== NULL) return false; // 内存分配失败
    // 本质上还是在结点p后面插入新结点，然后再将结点p和结点s的元素互换
    s->next = p -> next;
    p->next = s;
    s->data = p->data; // 将p中的元素复制到s
    p->data = elem; // p中的元素覆盖为插入的元素
    return true;
}

//指定结点的前操作：在指定p结点前面插入结点s
bool insertNodeBeforeNode(LinkedList &p,LinkedList &s){
    if(p == NULL || s == NULL) return false; // 结点不合法
    // 本质：结点p和结点s的元素互换
    s->next = p->next;
    p->next = s;
    ElemType  elem = p->data;
    p->data = s->data;
    s->data = elem;
    return true;
}

// 删除第i个位置的元素，并用e返回删除的元素：带头结点
bool deleteByPos(LinkedList &L,int pos,ElemType &elem){
    if( pos < 1)return false; // 位置不合法
    // 指针p指向当前扫描到的结点
    LNode* p;
    int j = 0; // 指针p所在的位置
    p = L; // 初始时指向头结点
    while(p != NULL && j< pos-1){
        p = p->next;
        j++;
    }
    if(p == NULL) return false; // 位置不合法
    if(p->next == NULL) return false; // 指针p已是最后一个结点
    LNode* s = p->next; // 指针s指向第i个位置所在的结点
    elem = s->data; // 将待删除的元素保存
    p->next = s->next; // 将指针p的下一个结点指向删除元素所在的结点的下一个结点
    free(s); // 释放删除结点所在的存储空间
    return true;
}

// 删除指定结点p
bool deleteNode(LNode* p){
    if(p == NULL) return p; //结点不合法
    if(p->next == NULL){
        // 当前结点p是最后一个结点，直接删除
        free(p);
    }
    // 本质还是将下一个结点的数据复制到删除的结点
    LNode* s = p -> next;
    p->data = s->data;
    p->next = s->next;
    free(s);
    return true;
}

// 打印链表中每一个元素
void printLinkedList(LinkedList L){
    if(L == NULL) return;
    // 临时结点
    LNode* p = L -> next;
    while(p != NULL){
        printf("%d ",p->data);
        p = p -> next;
    }
}

// 按位查找，返回第i个元素(带头结点)
LNode* findLinkedListByPos(LinkedList L,int pos){
    if(pos < 1) return NULL; // 判断位置是否合法
    LNode* p = L; // 指向当前结点
    int j=0; // 当前指针p是第几个结点
    while(p!= NULL && j < pos){ // 循环找到第pos个结点
        p = p->next;
        j++;
    }
    return p;
}

// 按值查找，找到数据为elem的结点(带头结点)
LNode* findByVal(LinkedList L,ElemType elem){
    LNode* p = L -> next;
    // 从第一个结点开始查找
    while(p!=NULL && p->data != elem){
        p = p->next;
    }
    return p;
}


int main() {
    LinkedList L;
    // 头插法建立单链表(带头结点)
//    insertLinkedListBefore(L);
//    // 打印链表中每一个元素
//    printLinkedList(L);

    // 尾插法建立单链表(带头结点)
    insertLinkedListAfter(L);
    printLinkedList(L);
    return 0;
}
